package code2101_2200.code80_90;

/**
 * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
 *
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 *
 * 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
 *
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 *
 * 输入：n = 2
 * 输出：1
 *
 * 输入：n = 5
 * 输出：5
 */
public class _2181fib {

    /**
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 35.2 MB     * , 在所有 Java 提交中击败了     *61.42%     * 的用户
     * @param n
     * @return
     */
    public int fib(int n) {
        final int mod = 1000000007;
        if(n<2)return n;
        int left = 0, right = 1;
        int now = 1;
        for (int i = 1; i < n; i++) {
            now = left+right;
            left = right;
            if(now>mod){
                right = now%mod;
            }else {
                right = now;
            }
        }
        return right;
    }

    /**
     * 字节跳动面试要求写出logN方法
     *
     * 使用矩阵快速幂可降低时间复杂度。直接计算M矩阵的n次幂，就可以得到F(n)的值。
     * 如果直接求取M的n次方，时间复杂度还是O(n)，可以定义矩阵乘法，然后使用快速幂算法求取
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 35.2 MB     * , 在所有 Java 提交中击败了     * 57.06%     * 的用户
     * @param n
     * @return
     */

    private final int mod = 1000000007;

    public int fib1(int n) {
        if(n<2)return n;
        int[][] q = {{1,1},{1,0}};
        int[][] res = pow(q,n-1);
        return res[0][0];
    }

    private int[][] pow(int[][] a, int n) {
        int[][] ret = {{1,0},{0,1}};
        while (n>0){
            if((n&1)==1){
                ret = multiply(ret,a);
            }
            n>>=1;
            a = multiply(a,a);
        }
        return ret;
    }

    private int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = (int)(((long)a[i][0]*b[0][j]+(long)a[i][1]*b[1][j])%mod);
            }
        }
        return c;
    }

}
